"""
链表 (Linked List) - Python实现
非连续内存，通过引用连接，动态大小，插入删除O(1)
"""

class Node:
    """链表节点"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """单链表"""
    def __init__(self):
        self.head = None
        self.size = 0
    
    def append(self, data):
        """在末尾添加"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1
    
    def insert_at_head(self, data):
        """在头部插入"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def delete(self, data):
        """删除第一个匹配的节点"""
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                return
            current = current.next
    
    def __str__(self):
        result = []
        current = self.head
        while current:
            result.append(str(current.data))
            current = current.next
        return " → ".join(result)

# 应用场景1: LRU缓存
class LRUCache:
    """最近最少使用缓存"""
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.order = LinkedList()
    
    def get(self, key):
        if key in self.cache:
            # 移到最前（最近使用）
            return self.cache[key]
        return None
    
    def put(self, key, value):
        if len(self.cache) >= self.capacity:
            # 删除最久未使用
            pass
        self.cache[key] = value

def main():
    print("╔════════════════════════════════════════╗")
    print("║   链表 (Linked List) - Python实现      ║")
    print("╚════════════════════════════════════════╝")
    
    ll = LinkedList()
    ll.append(10)
    ll.append(20)
    ll.append(30)
    ll.insert_at_head(5)
    print(f"\n链表: {ll}")
    print(f"大小: {ll.size}")
    
    ll.delete(20)
    print(f"删除20后: {ll}")
    
    print("\n✅ 优势: 动态大小，插入删除O(1)")
    print("⚠️ 局限: 访问O(n)，额外指针空间")
    print("💡 应用: LRU缓存、撤销功能、播放列表")

if __name__ == "__main__":
    main()
